// https://leetcode.cn/problems/diameter-of-binary-tree/
// Created by ade on 2022/8/9.
//

class Solution {
public:
    // 暴力可以解决
    int d = 0;

    int diameterOfBinaryTree1(TreeNode *root) {
        dfs(root);
        return d;
    }

    void dfs(TreeNode *node) {
        if (!node) return;
        int left = getHeight(node->left);
        int right = getHeight(node->right);
        d = max(left + right, d);
        dfs(node->left);
        dfs(node->right);
    }

    int getHeight(TreeNode *node) {
        if (!node) return 0;
        return max(getHeight(node->left), getHeight(node->right)) + 1;
    }

    // 优化版本，只需要遍历一次
    int diameterOfBinaryTree(TreeNode *root) {
        dfs1(root);
        return d;
    }

    int dfs1(TreeNode *node) {
        if (!node) return 0;
        int left = dfs1(node->left);
        int right = dfs1(node->right);
        d = max(d, left + right + 1);
        return max(left, right) + 1;
    }
};


int main() {
    Solution so;
    TreeNode *h1 = so.init();
    auto res = so.levelOrder(h1);
    for (auto items : res) {
        for (auto i : items) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}
